1558. Устройство РубГолдберг

Люси необходимо сконструировать устройство преобразования энергии РубГолдберг. Возможные преобразования описываются в формате “INPUT OUTPUT TIME”, где INPUT и OUTPUT представляют собой входную и выходную энергии, TIME – время преобразования энергии в секундах. В наличии имеются четыре типа энергий: “CHEMICAL”, “ELECTRIC”, “MECHANICAL” и “THERMAL”.

Время работы устройства должно быть как можно ближе к target секундам. Устройство состоит из последовательных преобразований энергии, где результат очередного преобразования подается на вход следующего. Начинать свою работу устройство может с любого типа энергии, но в конце всех преобразований должна получиться энергия last.

Необходимо найти наименьшую возможную разность между target и временем работы построенного устройства.

Вход. Первая строка каждого теста содержит количество преобразований n (1 ≤ n ≤ 50), а также значения target и last (1 ≤ target, last ≤ 250000). Следующие n строк описывают преобразования энергии в формате “INPUT OUTPUT TIME”.

Выход. Для каждого теста в отдельной строке вывести наименьшую возможную разность между target и временем работы построенного устройства.

Пример входа	Пример выхода
1 12 CHEMICAL CHEMICAL CHEMICAL 5 3 123 THERMAL CHEMICAL THERMAL 6 THERMAL CHEMICAL 3 THERMAL CHEMICAL 5 3 123456 ELECTRIC CHEMICAL MECHANICAL 12 MECHANICAL THERMAL 13 THERMAL CHEMICAL 14	2 0 123456

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Закодируем типы энергий номером индекса в массиве energy[] = {'C','E','M','T'}. Например, механической энергии будет соответствовать 2. Информацию о правилах преобразования энергии (их не более 50) занесем в массив prt[50][3], где prt[i] содержит массив из трех чисел: коды входной и выходной энергии, а также время преобразования. Например, правило "CHEMICAL THERMAL 6" будет представлено массивом {0, 3, 6} (0 = CHEMICAL, 3 = THERMAL).

Заведем двумерный массив dp, в котором dp[time][e] равно 1, если ровно через time секунд можно получить энергию e. Иначе присвоим dp[time][e] = 0. Поскольку можно начинать преобразования с любого типа энергии, положим dp[0][i] = 1 для каждого из четырех типов энергии (i = 0, 1, 2, 3). Последовательно вычисляем значения dp[time][e], time = 1, 2, 3, …, 2 * target, 1 £ e £ 4. Для каждой ячейки dp[time][e] перебираем все правила преобразования. Пусть k - ое правило, информация о котором находится в prt[k], начинается с энергии e = prt[k][0]. Тогда в time + prt[k][2] секунд можно получить энергию prt[k][1], поэтому положим

dp[time + prt[k][2]] [prt[k][1]] = 1

Вычислим код энергии last в переменной j. Просматриваем значения dp[target + i][j] и dp[target – i][j] i = 0, 1, 2, 3, . . . , и как только одно из них станет равным 1, возвращаем i.

Реализация алгоритма

Объявим глобальные массивы.

char dp[MAX][4];

int prt[50][3];

Функция howClose возвращает наименьшую возможную разность между target и временем работы построенного устройства.

int howClose(int target, string last)

{

int i, j, k, time;

char energy[] = {'C','E','M','T'}, from[11], to[11];

Закодируем правила преобразования энергии в массиве prt как указано в анализе задачи.

for(i = 0; i < n; i++)

{

scanf("%s %s %d\n",from,to,&time);

Находим, к какому типу энергии относится from.

for(j = 0; j < 4; j++) if (from[0] == energy[j]) break;

prt[i][0] = j;

Находим, к какому типу энергии относится to.

for(j = 0; j < 4; j++) if (to[0] == energy[j]) break;

prt[i][1] = j;

prt[i][2] = time;

}

memset(dp,0,sizeof(dp));

Поскольку можно начинать преобразования с любого типа энергии, положим dp[0][i] = 1 для каждого из четырех типов энергии (i = 0, 1, 2, 3).

for(i = 0; i < 4; i++) dp[0][i] = 1;

Для i - ой секунды

for(i = 0; i < 2 * target; i++)

Для j - ого типа энергии

for(j = 0; j < 4; j++)

if (dp[i][j])

Для всех правил преобразования

for(k = 0; k < n; k++)

if (prt[k][0] == j) dp[i+prt[k][2]][prt[k][1]] = 1;

В переменной j находим код энергии last, которая должна получиться в результате всех преобразований.

for(j = 0; j < 4; j++) if (last[0] == energy[j]) break;

Ищем ближайшую к target секунду (как справа так и слева от нее), в которую можно получить энергию last, имеющую код j.

for(i = 0; ; i++)

{

if (dp[target+i][j]) break;

if (dp[target-i][j]) break;

}

return i;

}

Основная часть программы.

while(scanf("%d %d %s\n",&n,&target,last) == 3)

{

res = howClose(target,last);

printf("%d\n",res);

}